import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicReference;

/**
 * @Projectname: HandTornQuestions
 * @Filename: LRU
 * @Author: FANSEA
 * @Date:2024/10/28 19:41
 */
public class LRUCache<K,V> {
    private final int capacity;
    private Node<V> head;
    private Node<V> tail;
//    private K tailKey;
    private final Map<K,Node<V>> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }

    // 插入元素
    public void insert(K key,V value){
        Node<V> node = new Node<>(value);
        if (map.isEmpty()){
            map.put(key,node);
            head = node;
            tail = node;
            return;
        }
        // 判断当前key是否存在，如果存在则替换值
        if (map.containsKey(key)){
            map.put(key,node);
            return;
        }
        // 如果空间大于设定值
        if (map.size()==capacity){
            // 移除最后一个元素
//            map.remove(tailKey);
            removeMapKey(tail.val);
            tail = tail.pre;
            tail.next = null;
        }
        node.next = head;
        head.pre = node;
        head = node;
        map.put(key,node);
    }

    public V get(K key){
        if (!map.containsKey(key)){
            return null;
        }
        // 移动当前元素到最前面
        Node<V> node = map.get(key);
        if (node!=head){
            if (node == tail){
                tail = node.pre;
            }
            node.pre = node.next;
            node.next = head;
            head = node;
        }
        return node.val;
    }


    public void remove(K key){
        if (!map.containsKey(key)){
            return;
        }
        Node<V> x = map.get(key);
        Node<V> pre = x.pre;
        if (pre!=null){
            pre.next = x.next;
        }
        map.remove(key);
    }

    private void removeMapKey(V value){
        for (Map.Entry<K, Node<V>> entry : map.entrySet()){
            if (entry.getValue().val.equals(value)){
                map.remove(entry.getKey());
                break;
            }
        }

    }

    private static class Node<V> {
        V val;
        Node<V> next;
        Node<V> pre;
        public Node(V val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        LRUCache<String,String> lruCache = new LRUCache<>(3);
        lruCache.insert("a","a");
        lruCache.insert("b","b");
        lruCache.insert("c","c");
        lruCache.insert("d","d"); // 移除a
        lruCache.insert("a","a"); // 移除b
        System.out.println(lruCache.get("a"));
        System.out.println(lruCache.get("b")); // null
        System.out.println(lruCache.get("c"));
        System.out.println(lruCache.get("d")); // d->c->a
        System.out.println("head="+lruCache.head.val);
    }
}
